package com.wwz.leetcode;

import com.wwz.common.TreeNode;
import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * <p>Description:伴鱼考题</p>
 * <p>Copyright: Copyright (c)2020</p>
 * <P>Created Date :2020-10-21</P>
 * <P>@version 1.0</P>
 */
public class LeetCode113 {

//    给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
//    输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
//    输出：[[5,4,11,2],[5,8,4,5]]


    @Test
    public void test() {
        // pathSum2(new TreeNode(5, new TreeNode(4, new TreeNode(11, new TreeNode(7, null, null), new TreeNode(2, null, null)), null), new TreeNode(8, new TreeNode(13, null, null), new TreeNode(4, new TreeNode(5, null, null), new TreeNode(1, null, null)))), 22);
        pathSum2(new TreeNode(0, null, null), 1);
    }

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> res = new ArrayList();
        solution(root, sum, res, new ArrayList<Integer>());
        return res;
    }

    public void solution(TreeNode root, int sum, List<List<Integer>> res, List<Integer> path) {
        if (root == null) {
            return;
        }
        sum -= root.val;
        // 到叶子节点了
        if (root.left == null && root.right == null) {
            // 是否满足条件
            if (sum == 0) {
                path.add(root.val);
                res.add(new ArrayList<Integer>(path));
                // 向上回溯
                path.remove(path.size() - 1);
            }
            return;
        }
        path.add(root.val);
        solution(root.left, sum, res, path);
        solution(root.right, sum, res, path);
        // 向上回溯
        path.remove(path.size() - 1);

    }


    public List<List<Integer>> pathSum2(TreeNode root, int sum) {
        List<List<Integer>> resList = new ArrayList();
        solution2(root, sum, resList, new ArrayList<Integer>());
        return resList;
    }

    private void solution2(TreeNode root, int sum, List<List<Integer>> resList, List<Integer> path) {
        if (root == null) {
            return;
        }
        int val = root.val;
        sum -= val;
        path.add(val);
        // 到叶子节点了 且满足条件
        if (root.left == null && root.right == null && sum == 0) {
            resList.add(new ArrayList<Integer>(path));
        }
        solution2(root.left, sum, resList, path);
        solution2(root.right, sum, resList, path);
        path.remove(path.size() - 1);
    }

}
